#ifndef _M_TYPES_H_
#define _M_TYPES_H_
#include <string.h>

#define True  1
#define False 0
#ifdef NULL
#undef NULL
#endif
#define NULL ((void *)0)

typedef unsigned char   UInt8;
typedef unsigned short  UInt16;
typedef unsigned int    UInt32;

typedef signed char     Int8;
typedef signed short    Int16;
typedef signed int      Int32;

typedef UInt8           Bool;

typedef double          Double;
typedef float           Float;

#endif  // _M_TYPES_H_

/**
 * MGroup 枚举值
 */
typedef enum MGroupTag
{
    kGroupCommon     = 0,  // 公共
    kGroupList       = 1,  // 列表
    kGroupDataCenter = 2,  // 数据中心
} MGroup;

#define MakeErrCode(group, code) (-((group << 16) | (code & 0xffff)))

/**
 * MErrCode 错误码枚举值
 */
typedef enum MErrCodeTag
{
/**公共错误码 */
    kErrCodeSucc =  0,  // 执行成功

    kErrCodeElse          = MakeErrCode(kGroupCommon, 1),  // 其他错误
    kErrCodeParamsErr     = MakeErrCode(kGroupCommon, 2),  // 参数错误
    kErrCodeMallocFail    = MakeErrCode(kGroupCommon, 3),  // 分配空间失败
    kErrCodeGetLockErr    = MakeErrCode(kGroupCommon, 4),  // 取锁错误
    kErrCodeNotCreate     = MakeErrCode(kGroupCommon, 5),  // 未创建
    kErrCodeItemNotExist  = MakeErrCode(kGroupCommon, 6),  // 成员不存在
    kErrCodeHandleInvalid = MakeErrCode(kGroupCommon, 7),  // 句柄无效
    kErrCodeOutOfSpace    = MakeErrCode(kGroupCommon, 8),  // 空间不足
} MErrCode;

#define ALLOC_BASE_SIZE    256  // 动态内存的大小，供用户分配的总额 单位：B (需要是4的倍数)
#define BLOCK_SIZE 4
#define BLOCK_COUNT (ALLOC_BASE_SIZE / BLOCK_SIZE)

static Bool   is_init_;  // 是否初始化
static UInt32 memory_[BLOCK_COUNT];  // 内存区起始
static UInt32 *memory_end_ = &memory_[BLOCK_COUNT - 1];  // 内存区结束
static UInt32 *last_block_adr_ = NULL;  // 最近操作的内存地址
static Int32  uesd_block_cnt_ = 0;  // 已使用的内存块个数
#include <stdio.h>

void MMemoryInit(void)
{
    UInt32 block_info;

    block_info = BLOCK_COUNT - 2;

    // 填充内存块信息
    *memory_ = block_info;
    *memory_end_ = block_info;

    last_block_adr_ = memory_;

    uesd_block_cnt_ = 2;

    is_init_ = True;
}

void MMemoryFini(void)
{
    is_init_ = False;
}

static void* do_alloc(UInt32 *start, UInt32 *end, UInt32 size)
{
    void *ret_adr = NULL;

    UInt32 *look_adr   = start;
    UInt32  block_need = size / BLOCK_SIZE + (size % BLOCK_SIZE > 0 ? 1 : 0);
    UInt32  block_size = 0;
    Bool    block_used = False;

    while (look_adr < end)  // 从之前返回的内存块找到尾
    {
        block_used = (*look_adr) >> 31;
        block_size = (*look_adr) & 0x7FFFFFFF;

        if (! block_used && block_size >= block_need)  // 找到了
        {
            UInt32 left_size = block_size - block_need;

            if (left_size > 2)  // 多出来的内存值得拆分
            {
                UInt32 new_block_size = left_size - 2;  // 新内存块的大小

                // 更新当前内存块的信息
                *look_adr = block_need | 0x80000000;
                *(look_adr + block_need + 1) = *look_adr;
                last_block_adr_ = look_adr;

                // 设置新内存块的信息
                look_adr += block_need + 2;  // 移到新的内存块
                *look_adr = new_block_size;
                *(look_adr + new_block_size + 1) = *look_adr;
                uesd_block_cnt_ += block_need + 2;
            }
            else  // 多出来的内存不值得拆分，一并分配出来
            {
                // 更新当前内存块的信息
                *look_adr = block_size | 0x80000000;
                *(look_adr + block_size + 1) = *look_adr;
                last_block_adr_ = look_adr;
                uesd_block_cnt_ += block_size;
            }

            ret_adr = last_block_adr_ + 1;
            break;
        }

        look_adr += block_size + 2;  // 前往下一个内存块
    }

    return ret_adr;
}

void* MMalloc(UInt32 size)
{
    void *ret_adr = NULL;

    if (is_init_ && size > 0)
    {

            // 先从上次返回的内存块开始找
            ret_adr = do_alloc(last_block_adr_, memory_end_, size);

            if (ret_adr == NULL)  // 没找到，再从头找到之前返回的内存块
            {
                ret_adr = do_alloc(memory_, last_block_adr_, size);
            }


    }

    return ret_adr;
}

void MFree(void *space)
{
    if (is_init_)
    {
        if ((UInt32 *)space > memory_ && (UInt32 *)space < memory_end_)
        {
            UInt32 *block_adr = (UInt32 *)space - 1;

            // 更新当前内存块的信息
            *block_adr &= 0x7FFFFFFF;
            *(block_adr + *block_adr + 1) = *block_adr;
            uesd_block_cnt_ -= *block_adr;

            // 尝试合并下个内存块
            UInt32 *next_adr = block_adr + *block_adr + 2;
            if (next_adr < memory_end_ && (*next_adr) >> 31 == 0)  // 下个内存块空闲，开始合并
            {
                *block_adr += *next_adr + 2;
                *(block_adr + *block_adr + 1) = *block_adr;
                *next_adr = 0;
                *(next_adr - 1) = 0;
                uesd_block_cnt_ -= 2;
            }

            last_block_adr_ = block_adr;

            // 尝试合并上个内存块
            UInt32 *prev_adr = block_adr - 1;
            if (prev_adr > memory_ && (*prev_adr) >> 31 == 0)  // 上个内存块空闲，开始合并
            {
                // 移到上个内存块的头部
                prev_adr -= (*prev_adr) + 1;

                // 更新内存块信息
                *prev_adr += *block_adr + 2;
                *(prev_adr + *prev_adr + 1) = *prev_adr;

                *block_adr = 0;
                *(block_adr - 1) = 0;

                last_block_adr_ = prev_adr;
                uesd_block_cnt_ -= 2;
            }
        }

    }
}

Int32 MMemoryGetTotalSpace(Int32* total_size)
{
    if (total_size == NULL)
    {
        return kErrCodeParamsErr;
    }

    if (! is_init_)
    {
        return kErrCodeNotCreate;
    }

    *total_size = ALLOC_BASE_SIZE;

    return kErrCodeSucc;
}

Int32 MMemoryGetUsedSize(Int32* used_size)
{
    if (used_size == NULL)
    {
        return kErrCodeParamsErr;
    }

    if (! is_init_)
    {
        return kErrCodeNotCreate;
    }

    Int32 result = kErrCodeElse;


        *used_size = uesd_block_cnt_ * BLOCK_SIZE;
        result = kErrCodeSucc;


    return result;
}

Int32 MMemoryGetPercentage(UInt8* percentage)
{
    if (percentage == NULL)
    {
        return kErrCodeParamsErr;
    }

    if (! is_init_)
    {
        return kErrCodeNotCreate;
    }

    Int32 result = kErrCodeElse;


        *percentage = (uesd_block_cnt_ * BLOCK_SIZE * 100) / ALLOC_BASE_SIZE;
        result = kErrCodeSucc;


    return result;
}

void print_memory()
{
    Int32 used_size = 0;

    MMemoryGetUsedSize(&used_size);

    printf("used size: %d\n", used_size / 4);

    for (Int32 i = 0; (i < (((ALLOC_BASE_SIZE / 4) % 16 > 0) ? ((ALLOC_BASE_SIZE / 4) / 16 + 1): ((ALLOC_BASE_SIZE / 4) / 16))); i ++)
    {
        for (Int32 j = 0; j < 16; j ++)
        {
            Int32 idx = i * 16 + j;

            printf("\033[44m0x%08X \033[44m", (unsigned int)&memory_[idx]);
        }
        printf("\033[40m\n");
        for (Int32 j = 0; j < 16; j ++)
        {
            Int32 idx = i * 16 + j;

            if (idx >= ALLOC_BASE_SIZE / 4)
                break;
            if (memory_[idx] > 0)
                printf("\033[33m0x%08X \033[37m", memory_[idx]);
            else
                printf("0x%08X ", memory_[idx]);
        }
        printf("\n");
    }
}


int main(void)
{
    MMemoryInit();

    print_memory();

    // // test1. 连续分配内存，观察内存块变化
    // printf("malloc %d, ret=%p\n", 16, MMalloc(16));
    // print_memory();
    // printf("malloc %d, ret=%p\n", 17, MMalloc(17));
    // print_memory();
    // printf("malloc %d, ret=%p\n", 1, MMalloc(1));
    // print_memory();
    // // test2. 连续分配、释放内存，观察内存块变化
    // void *p = NULL;
    // p = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p);
    // print_memory();
    // printf("free %p\n", p);
    // MFree(p);
    // print_memory();
    // p = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p);
    // print_memory();
    // printf("free %p\n", p);
    // MFree(p);
    // print_memory();
    // // test3. 连续分配、释放中间的内存，观察内存块变化
    // void *p1, *p2, *p3 = NULL;
    // p1 = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p1);
    // print_memory();
    // p2 = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p2);
    // print_memory();
    // p3 = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p3);
    // print_memory();
    // printf("free %p\n", p2);
    // MFree(p2);
    // print_memory();
    // p2 = MMalloc(16);
    // printf("malloc %d, ret=%p\n", 16, p2);
    // print_memory();
    // test4. 连续分配、释放两端的内存，再释放中间内存，观察内存块变化
    void *p1, *p2, *p3, *p4 = NULL;
    p1 = MMalloc(16);
    printf("malloc %d, ret=%p\n", 16, p1);
    print_memory();
    p2 = MMalloc(16);
    printf("malloc %d, ret=%p\n", 16, p2);
    print_memory();
    p3 = MMalloc(16);
    printf("malloc %d, ret=%p\n", 16, p3);
    print_memory();
    p4 = MMalloc(16);
    printf("malloc %d, ret=%p\n", 16, p4);
    print_memory();
    printf("free %p\n", p1);
    MFree(p1);
    print_memory();
    printf("free %p\n", p3);
    MFree(p3);
    print_memory();
    printf("free %p\n", p2);
    MFree(p2);
    print_memory();
    printf("free %p\n", p4);
    MFree(p4);
    print_memory();
    // // test5. 连续分配1字节，直到分配失败，观察内存块变化
    // void *p = NULL;
    // while (p = MMalloc(1))
    // {
    //     Int32 size = 0;

    //     MMemoryGetUsedSize(&size);
    //     printf("malloc 1\n");
    //     print_memory();
    // }

    MMemoryFini();

    return 0;
}
